package cn.bellychang.bobo.linkedlist;

import cn.bellychang.bobo.arraylist.Iterator;

/**
 * @author ChangLiang
 * @date 2020/9/9
 */
public class LinkedList<E> {

    private int size;

    Node head;

    public LinkedList() {
        head = new Node();

        // 使用dummyHead 更有语义的表达
        /*Node<E> dummyHead = new Node<>(null, null);
        head = dummyHead;*/
    }

    public int getSize() {
        return size;
    }

    public void add(int index, E e) {
        checkAddIndex(index);
        Node newNode = new Node();
        newNode.value = e;

        if (size == 0) {
            // 为空时处理
            head = newNode;
        } else {
            // 不为空时处理
            if (index == 0) {
                newNode.next = head;
                head = newNode;
            } else if (index == size) {
                Node prevNode = getNode(index - 1);
                prevNode.next = newNode;
            } else {
                Node prevNode = getNode(index - 1);
                Node afterNode = prevNode.next;
                prevNode.next = newNode;
                newNode.next = afterNode;
            }
        }
        size++;
    }

    public void addLast(E e) {
        add(size, e);
    }

    public void addFirst(E e) {
        add(0, e);
    }

    public E get(int index) {
        checkGetOrRemoveIndex(index);
        return getNode(index).value;
    }

    public E getFirst() {
        return get(0);
    }

    public E getLast() {
        return get(size);
    }

    public E remove(int index) {
        checkAddIndex(index);

        if (size == 0) {
            throw new RuntimeException("empty linkedlist");
        } else {
            Node temp = getNode(index);
            if (index == 0) {
                head = head.next;
            } else if (index == size - 1) {
                Node prevNode = getNode(index - 1);
                prevNode.next = null;
            } else {
                Node prevNode = getNode(index - 1);
                prevNode.next = temp.next;
            }
            size--;
            return temp.value;
        }
    }

    public E removeFirst() {
        return remove(0);
    }

    public E removeLast() {
        return remove(size - 1);
    }

    private Node getNode(int index) {
        int count = 0;
        checkAddIndex(index);
        Node tmp = head;
        while (count < index) {
            tmp = tmp.next;
            count++;
        }
        return tmp;
    }

    private void checkAddIndex(int index) {
        if (index < 0 || index > size) {
            throw new RuntimeException("index out of bound");
        }
    }

    private void checkGetOrRemoveIndex(int index) {
        if (index < 0 || index >= size) {
            throw new RuntimeException("index out of bound");
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Iterator<E> iterator = this.iterator();
        while (iterator.hasNext()) {
            builder.append(iterator.next());
            if (iterator.hasNext()) {
                builder.append("->");
            }
        }
        return builder.toString();
    }

    public Iterator<E> iterator() {
        return new Iterator<E>() {

            Node node = head;

            @Override
            public boolean hasNext() {
                if (size == 0) {
                    return false;
                }
                return node != null;
            }

            @Override
            public E next() {
                E value = node.value;
                node = node.next;
                return value;
            }
        };
    }

    class Node {

        private E value;

        private Node next;
    }
}
